﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class ConundrumReloaded
{
    public int minimumLiars(string answers)
    {
        char[] arr = answers.ToCharArray();
        int len = answers.Length;

        bool link = false;
        List<string> subList = new List<string>();
        if (answers.Contains("?"))
        {
            foreach (string sub in answers.Split(new char[] { '?' }))
            {
                if (sub != "") subList.Add(sub);
            }
            if (answers.First() != '?' && answers.Last() != '?')
            {
                string last = subList.Last();
                subList.RemoveAt(subList.Count - 1);
                subList[0] = last + subList[0];
            }
        }
        else
        {
            link = true;
            subList.Add(answers + answers.First());
        }

        int cntL = 0;
        foreach (string sub in subList)
        {
            bool prevH1 = true;
            int cntL1 = 0;
            for (int i = 1; i < sub.Length; i++)
            {
                if (prevH1)
                {
                    if (arr[i - 1] == 'H')
                    {
                        prevH1 = true;
                    }
                    else
                    {
                        cntL1++;
                        prevH1 = false;
                    }
                }
                else
                {
                    if (arr[i - 1] == 'H')
                    {
                        cntL1++;
                        prevH1 = false;
                    }
                    else
                    {
                        prevH1 = true;
                    }
                }
            }

            bool prevH2 = false;
            int cntL2 = 1;
            for (int i = 1; i < sub.Length; i++)
            {
                if (prevH2)
                {
                    if (arr[i - 1] == 'H')
                    {
                        prevH2 = true;
                    }
                    else
                    {
                        cntL2++;
                        prevH2 = false;
                    }
                }
                else
                {
                    if (arr[i - 1] == 'H')
                    {
                        cntL2++;
                        prevH2 = false;
                    }
                    else
                    {
                        prevH2 = true;
                    }
                }
            }

            if (link)
            {
                if (prevH1 != true && prevH2 != false) return -1;
            }

            cntL += Math.Min(cntL1, cntL2);
        }
        return cntL;
    }
}

public class IncrementingSequence
{
    public string canItBeDone(int k, int[] A)
    {
        SortedList<int, List<int>> kList = new SortedList<int, List<int>>();
        for (int i = 0; i < k; i++)
        {
            kList[i] = new List<int>();
        }
        foreach (int a in A)
        {
            int v = a - 1;
            int r = v % k;
            int d = v / k;
            kList[r].Add(d);
        }
        for (int i = 0; i < k; i++)
        {
            int len = ((A.Length - 1 - i) / k) + 1;
            if (kList[i].Count != len) return "IMPOSSIBLE";
            int cnt = 0;
            foreach (int d in kList[i].OrderBy(p => p))
            {
                if (d > cnt) return "IMPOSSIBLE";
                cnt++;
            }
        }
        return "POSSIBLE";
    }
}

public class AddMultiply
{

    public int[] makeExpression(int y)
    {
        int[] arr = new int[3];
        for (int i = -1000; i <= 1000; i++)
        {
            if (i == 0 || i == 1) continue;
            for (int j = -1000; j <= 1000; j++)
            {
                if (j == 0 || j == 1) continue;
                for (int k = -1000; k <= 1000; k++)
                {
                    if (k == 0 || k == 1) continue;
                    if (i * j + k == y)
                    {
                        arr[0] = i;
                        arr[1] = j;
                        arr[2] = k;
                        return arr;
                    }
                }
            }
        }
        return arr;

    }
}

